Convolution of impulse response functions with an input signals has a wide variety of applications, including, e.g., audio and video signal processing, sonar and radar, and general digital signal processing (DSP) applications. One such example is the convolution of audio signals to simulate the acoustic effect of an environment, whereby a source signal may be convolved with a finite impulse response (FIR) function that models the acoustic response of the environment. A practical application of such audio signal convolution is the real-time synthesis of sounds in a simulation, such as a video game virtual environment, in which a pre-computed impulse response function that models the acoustic characteristics of a virtual room may be convolved with an input source signal in real-time to simulate the virtual environment's acoustics. A variety of conventional techniques are available for performing convolution of such signals.
One such technique is direct convolution in the time domain of the functions corresponding to the input signal and impulse response filter. However, the computational cost of performing such convolution can be very high and the computation time for performing such operations increases linearly with filter length (i.e., t∝N2, where t is the computation time and N is the filter length or number of sampled points in the impulse response function). As a result, direction convolution in the time domain is unsuitable for many real-time applications, particularly when the impulse response function is of relatively long duration.
In light of the drawbacks associated with direct convolution, a variety of frequency domain techniques have been proposed which involve generating the frequency spectra of the time domain signals in order to take advantage of the concept that convolution in the time domain is replaced with point-wise multiplication in the frequency domain. The computation time scales logarithmically with filter length (i.e., t∝N log2N) rather than linearly, thereby providing a significant computational cost advantage over direct time domain techniques if the sample size is large enough.
Frequency domain convolution techniques typically involve a digitally sampled impulse response function, which may be pre-computed, a digitally sampled input signal, and conversion of the sampled signals into the frequency domain with a discrete Fourier transform (DFT). The DFT is typically performed by using a Fast Fourier Transform (FFT) algorithm on the time domain input signal and impulse response, and each segment of the signal and impulse response may be zero-padded to avoid circular convolution. Point-wise multiplication of the complex valued input signal and impulse response spectra is performed, and the resulting product is converted back to the time domain by an inverse Fast Fourier Transform (IFFT) to generate the desired convolved and filtered signal as a function of time.
A variety of techniques have been proposed for performing frequency domain convolution of impulse functions with input signals. One challenge is that frequency domain convolution introduces an inherent latency since the segment of the input signal must be initially buffered and the frequency bins must be loaded before the convolution operations can be performed. In many real-time applications, it is common to address latency concerns with block processing by partitioning the impulse response function into smaller blocks before performing the frequency domain convolution. However, traditional partitioned methods still suffer from slow performance and/or latency when performing the convolution of long impulse responses.
Accordingly, there is a need in the art for methods and apparatus that perform accurate and fast convolution of a real-time source signal with minimal latency and a low computational cost. It is within this context that the present disclosure arises.